/*
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
 */
//3.测试
public class TestDemo {
    //合并两个有序链表（在“给定值x为基准将链表分割成两部分”这个之后）
    /*//这样子打出来是1 2 4：
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }

        //定义prev
        MySingleList.ListNode prev1=null;
        MySingleList.ListNode prev2=null;
        //定义新的头结点
        MySingleList.ListNode newHead=null;
        if(list1.val<=list2.val){
            newHead=list1;
            prev1=list1;
            list1=list1.next;
        }else{
            newHead=list2;
            prev2=list2;
            list2=list2.next;
        }

        while(list1!=null&&list2!=null){//有一个为空了就退出循环
            if(list1.val<list2.val){
                prev2.next=list1;//但这段代码会有一个错误：如果这个的上一次也是list1.val<list2.val，这一次也是list1.val<list2.val
                                //那么这一次肯定就不能prev2.next=list1而是prev1.next=list1下面的else里面的这个语句同理，所以我们要用一个变量tmp来记录
                                //代码变成tmp.next=list1或者tmp.next=list2（而且刚开始定义prev就是因为头结点newHead不能动，那么定义一个tmp代替头结点动不就行了
                prev1=list1;
                list1=list1.next;
            }else{
                prev1.next=list2;
                prev2=list2;
                list2=list2.next;
            }
        }
        return newHead;
    }*/
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
        //定义新的头结点
        MySingleList.ListNode newHead=new MySingleList.ListNode(-1);
        //定义tmp
        MySingleList.ListNode tmp=newHead;

        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                tmp.next=list1;
                list1=list1.next;
                //tmp=tmp.next;
            }else{
                tmp.next=list2;
                list2=list2.next;
                //tmp=tmp.next;
            }
            tmp=tmp.next;
        }
        if(list1!=null){
            tmp.next=list1;
        }
        if(list2!=null){
            tmp.next=list2;
        }
        return newHead.next;//newHead只是一个傀儡节点，链表合并从它的后驱开始
    }
    /*老师的代码：
     public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                               MySingleList.ListNode headB) {

        //定义一个 傀儡节点(虚拟节点)：头节点   此时涉及到了 获取静态内部类对象
        MySingleList.ListNode newH = new MySingleList.ListNode(-1);

        MySingleList.ListNode tmp= newH;

        while (headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                //tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                //tmp = tmp.next;
            }
            tmp = tmp.next;
        }
        if(headA != null) {
            tmp.next = headA;
        }
        if(headB != null) {
            tmp.next = headB;
        }
        return newH.next;
    }
     */

    //“求两个链表第一个共同节点”要用到的函数
    public static void createCut(MySingleList.ListNode headA,
                                 MySingleList.ListNode headB) {

        headB.next.next = headA.next.next.next;
    }

    public static void main(String[] args) {
        //测试头插法
        System.out.println("*****测试头插法*****");
        MySingleList mySingleList=new MySingleList();
        mySingleList.addFirst(1);
        mySingleList.addFirst(12);
        mySingleList.addFirst(32);
        mySingleList.addFirst(0);
        mySingleList.display();//0 32 12 1
        mySingleList.clear();
        mySingleList.display();//什么都没有

        //测试尾插法
        System.out.println("*****测试尾插法*****");
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.addLast(43);
        mySingleList.addLast(5);
        mySingleList.addLast(-24);
        mySingleList.display();//12 12 43 5 -24
        mySingleList.clear();
        mySingleList.display();//什么都没有

        //测试任意位置插入
        System.out.println("*****测试任意位置插入*****");
        mySingleList.addIndex(0,-1);
        mySingleList.addIndex(1,23);
        mySingleList.addIndex(1,54);
        mySingleList.addIndex(3,9);
        mySingleList.display();//-1 54 23 9

        //测试删除
        System.out.println("*****测试删除*****");
        mySingleList.remove(8);
        mySingleList.display();//没有您要删除的数据 -1 54 23 9
        mySingleList.remove(-1);
        mySingleList.display();//54 23 9
        mySingleList.remove(9);
        mySingleList.display();//54 23
        mySingleList.clear();
        mySingleList.display();//什么都没有

        //测试删除
        System.out.println("*****测试删除*****");
        mySingleList.addFirst(1);
        mySingleList.addFirst(1);
        mySingleList.addFirst(32);
        mySingleList.addFirst(1);
        mySingleList.addFirst(24);
        mySingleList.addFirst(1);
        mySingleList.display();//1 24 1 32 1 1
        mySingleList.removeAllKey(1);
        mySingleList.display();//24 32
        mySingleList.clear();
        mySingleList.display();//什么都没有

        //反转链表
        System.out.println("*****反转链表*****");
        mySingleList.addFirst(33);
        mySingleList.addFirst(9);
        mySingleList.addFirst(124);
        mySingleList.addFirst(32);
        mySingleList.addFirst(3);
        mySingleList.addFirst(13);
        mySingleList.display();//13 3 32 124 9 33
        MySingleList.ListNode head=mySingleList.head;
        MySingleList.ListNode newHead=mySingleList.reverseList(head);
        mySingleList.display(newHead);//33 9 124 32 3 13
        //因为“//找中间节点方法1”出现的空指针异常，所以要清空mySingleList
        mySingleList.clear();
        mySingleList.display();//什么都没有


        //找中间节点方法
        System.out.println("*****找中间元素方法*****");
        /*mySingleList.display(mySingleList.middleNode());-->函数middleNode地while循环里的cur=cur.next空指针异常  mySingleList的head已经在reverseList置为空了
        为什么mySingleList的head已经在reverseList置为空了？-->因为：
        MySingleList.ListNode head=mySingleList.head;
        MySingleList.ListNode newHead=mySingleList.reverseList(head);
        这里最终传入.reverseList函数的是head里面存的引用
        public ListNode reverseList(ListNode head) {}这个函数接到的形参就是指向第一个节点的引用
        所以在函数reverseList里面head.next=null;改变的是head的后驱，这里不能想当然地以为“head形参的改变不会影响head实参”
         */
        mySingleList.addFirst(33);
        mySingleList.addFirst(9);
        mySingleList.addFirst(124);
        mySingleList.addFirst(32);
        mySingleList.addFirst(3);
        mySingleList.addFirst(13);
        mySingleList.display();//13 3 32 124 9 33
        //方法1
        MySingleList.ListNode node=mySingleList.middleNode();
        if(node==null){
            System.out.println("链表为空");
        }else{
            System.out.println("中间节点是"+node.val);//中间节点是124
        }
        //方法2
        MySingleList.ListNode node1=mySingleList.middleNode1();
        if(node1==null){
            System.out.println("链表为空");
        }else{
            System.out.println("中间节点是"+node1.val);//中间节点是124
        }


        //求倒数第k个节点
        System.out.println("*****求倒数第k个节点*****");
        System.out.println(mySingleList.kthToLast(6));//13


        //给定值x为基准将链表分割成两部分
        System.out.println("*****给定值x为基准将链表分割成两部分*****");
        //System.out.println(mySingleList.partition(33));//MySingleList$ListNode@378bf509
        mySingleList.display(mySingleList.partition(33));//13 3 32 9 124 33


        //合并两个有序列表
        System.out.println("*****合并两个有序列表*****");
        MySingleList mySingleList1=new MySingleList();
        mySingleList1.addLast(1);
        mySingleList1.addLast(2);
        mySingleList1.addLast(4);
        mySingleList1.display();//1 2 4
        MySingleList mySingleList2=new MySingleList();
        mySingleList2.addLast(1);
        mySingleList2.addLast(3);
        mySingleList2.addLast(4);
        mySingleList2.display();//1 3 4
        MySingleList.ListNode newHead1=mergeTwoLists(mySingleList1.head,mySingleList2.head);
        new MySingleList().display(newHead1);


        //判断链表是不是回文链表
        System.out.println("*****判断链表是不是回文链表*****");
        MySingleList mySingleList3=new MySingleList();
        mySingleList3.addLast(12);
        mySingleList3.addLast(23);
        mySingleList3.addLast(34);
        mySingleList3.addLast(23);
        mySingleList3.addLast(12);
        System.out.println(mySingleList3.chkPalindrome());//true


        //求两个链表第一个共同节点
        System.out.println("*****求两个链表第一个共同节点*****");
        MySingleList mySingleList4 = new MySingleList();
        mySingleList4.addLast(12);
        mySingleList4.addLast(23);
        mySingleList4.addLast(34);
        mySingleList4.addLast(45);
        mySingleList4.addLast(56);
        mySingleList4.addLast(67);
        System.out.print(" mySingleList4:");
        mySingleList4.display();
        MySingleList mySingleList5 = new MySingleList();
        mySingleList5.addLast(13);
        mySingleList5.addLast(25);
        mySingleList5.addLast(35);
        mySingleList5.addLast(146);
        mySingleList5.addLast(156);
        System.out.print(" mySingleList5:");
        mySingleList5.display();
        System.out.println("======测试======");
        createCut(mySingleList4.head,mySingleList5.head);
        System.out.print(" mySingleList4:");
        mySingleList4.display();
        System.out.print(" mySingleList5:");
        mySingleList5.display();
        MySingleList.ListNode ret = new MySingleList().getIntersectionNode(mySingleList4.head,mySingleList5.head);
        System.out.println("相同的第一个节点："+ret.val);
    }



}
